home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS 1.31 / support / set / set.c next >
Encoding:
C/C++ Source or Header  |  1995-03-10  |  14.9 KB  |  793 lines  |  [TEXT/MPS ]
  1. /*    set.c
  2.  
  3.     The following is a general-purpose set library originally developed
  4.     by Hank Dietz and enhanced by Terence Parr to allow dynamic sets.
  5.     
  6.     Sets are now structs containing the #words in the set and
  7.     a pointer to the actual set words.
  8.     
  9.     Generally, sets need not be explicitly allocated.  They are
  10.     created/extended/shrunk when appropriate (e.g. in set_of()).
  11.     HOWEVER, sets need to be destroyed (free()ed) when they go out of scope
  12.     or are otherwise no longer needed.  A routine is provided to
  13.     free a set.
  14.     
  15.     Sets can be explicitly created with set_new(s, max_elem).
  16.     
  17.     Sets can be declared to have minimum size to reduce realloc traffic.
  18.     Default minimum size = 1.
  19.     
  20.     Sets can be explicitly initialized to have no elements (set.n == 0)
  21.     by using the 'empty' initializer:
  22.     
  23.     Examples:
  24.         set a = empty;    -- set_deg(a) == 0
  25.         
  26.         return( empty );
  27.     
  28.     Example set creation and destruction:
  29.     
  30.     set
  31.     set_of2(e,g)
  32.     unsigned e,g;
  33.     {
  34.         set a,b,c;
  35.         
  36.         b = set_of(e);        -- Creates space for b and sticks in e
  37.         set_new(c, g);        -- set_new(); set_orel() ==> set_of()
  38.         set_orel(g, &c);
  39.         a = set_or(b, c);
  40.         .
  41.         .
  42.         .
  43.         set_free(b);
  44.         set_free(c);
  45.         return( a );
  46.     }
  47.  
  48.     1987 by Hank Dietz
  49.     
  50.     Modified by:
  51.         Terence Parr
  52.         Purdue University
  53.         October 1989
  54.  
  55.     Made it smell less bad to C++ 7/31/93 -- TJP
  56. */
  57.  
  58. #include <stdio.h>
  59. #ifdef __cplusplus
  60. #ifndef __STDC__
  61. #define __STDC__
  62. #endif
  63. #endif
  64. #ifdef __STDC__
  65. #include <stdlib.h>
  66. #else
  67. #include <malloc.h>
  68. #endif
  69. #include <string.h>
  70.  
  71. #include "set.h"
  72.  
  73. /* elems can be a maximum of 32 bits */
  74. static unsigned bitmask[] = {
  75.     0x00000001, 0x00000002, 0x00000004, 0x00000008,
  76.     0x00000010, 0x00000020, 0x00000040, 0x00000080,
  77.     0x00000100, 0x00000200, 0x00000400, 0x00000800,
  78.     0x00001000, 0x00002000, 0x00004000, 0x00008000,
  79. #if !defined(PC) || defined(__WATCOMC__)
  80.     0x00010000, 0x00020000, 0x00040000, 0x00080000,
  81.     0x00100000, 0x00200000, 0x00400000, 0x00800000,
  82.     0x01000000, 0x02000000, 0x04000000, 0x08000000,
  83.     0x10000000, 0x20000000, 0x40000000, 0x80000000
  84. #endif
  85. };
  86.  
  87. set empty = set_init;
  88. static unsigned min=1;
  89.  
  90. #define StrSize        200
  91.  
  92. #ifdef MEMCHK
  93. #define CHK(a)                    \
  94.     if ( a.setword != NULL )    \
  95.       if ( !valid(a.setword) )    \
  96.         {fprintf(stderr, "%s(%d): invalid set\n",__FILE__,__LINE__); exit(-1);}
  97. #else
  98. #define CHK(a)
  99. #endif
  100.  
  101. /*
  102.  * Set the minimum size (in words) of a set to reduce realloc calls
  103.  */
  104. void
  105. #ifdef __STDC__
  106. set_size( unsigned n )
  107. #else
  108. set_size( n )
  109. unsigned n;
  110. #endif
  111. {
  112.     min = n;
  113. }
  114.  
  115. unsigned int
  116. #ifdef __STDC__
  117. set_deg( set a )
  118. #else
  119. set_deg( a )
  120. set a;
  121. #endif
  122. {
  123.     /* Fast compute degree of a set... the number
  124.        of elements present in the set.  Assumes
  125.        that all word bits are used in the set
  126.        and that SETSIZE(a) is a multiple of WORDSIZE.
  127.     */
  128.     register unsigned *p = &(a.setword[0]);
  129.     register unsigned *endp = &(a.setword[a.n]);
  130.     register unsigned degree = 0;
  131.  
  132.     CHK(a);
  133.     if ( a.n == 0 ) return(0);
  134.     while ( p < endp )
  135.     {
  136.         register unsigned t = *p;
  137.         register unsigned *b = &(bitmask[0]);
  138.         do {
  139.             if (t & *b) ++degree;
  140.         } while (++b < &(bitmask[WORDSIZE]));
  141.         p++;
  142.     }
  143.  
  144.     return(degree);
  145. }
  146.  
  147. set
  148. #ifdef __STDC__
  149. set_or( set b, set c )
  150. #else
  151. set_or( b, c )
  152. set b;
  153. set c;
  154. #endif
  155. {
  156.     /* Fast set union operation */
  157.     /* resultant set size is max(b, c); */
  158.     set *big;
  159.     set t;
  160.     unsigned int m,n;
  161.     register unsigned *r, *p, *q, *endp;
  162.  
  163.     CHK(b); CHK(c);
  164.     t = empty;
  165.     if (b.n > c.n) {big= &b; m=b.n; n=c.n;} else {big= &c; m=c.n; n=b.n;}
  166.     set_ext(&t, m);
  167.     r = t.setword;
  168.  
  169.     /* Or b,c until max of smaller set */
  170.     q = c.setword;
  171.     p = b.setword;
  172.     endp = &(b.setword[n]);
  173.     while ( p < endp ) *r++ = *p++ | *q++;    
  174.  
  175.     /* Copy rest of bigger set into result */
  176.     p = &(big->setword[n]);
  177.     endp = &(big->setword[m]);
  178.     while ( p < endp ) *r++ = *p++;
  179.  
  180.     return(t);
  181. }
  182.  
  183. set
  184. #ifdef __STDC__
  185. set_and( set b, set c )
  186. #else
  187. set_and( b, c )
  188. set b;
  189. set c;
  190. #endif
  191. {
  192.     /* Fast set intersection operation */
  193.     /* resultant set size is min(b, c); */
  194.     set t;
  195.     unsigned int n;
  196.     register unsigned *r, *p, *q, *endp;
  197.  
  198.     CHK(b); CHK(c);
  199.     t = empty;
  200.     n = (b.n > c.n) ? c.n : b.n;
  201.     if ( n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  202.     set_ext(&t, n);
  203.     r = t.setword;
  204.  
  205.     /* & b,c until max of smaller set */
  206.     q = c.setword;
  207.     p = b.setword;
  208.     endp = &(b.setword[n]);
  209.     while ( p < endp ) *r++ = *p++ & *q++;    
  210.  
  211.     return(t);
  212. }
  213.  
  214. set
  215. #ifdef __STDC__
  216. set_dif( set b, set c )
  217. #else
  218. set_dif( b, c )
  219. set b;
  220. set c;
  221. #endif
  222. {
  223.     /* Fast set difference operation b - c */
  224.     /* resultant set size is size(b) */
  225.     set t;
  226.     unsigned int n;
  227.     register unsigned *r, *p, *q, *endp;
  228.  
  229.     CHK(b); CHK(c);
  230.     t = empty;
  231.     n = (b.n <= c.n) ? b.n : c.n ;
  232.     if ( b.n == 0 ) return t;        /* TJP 4-27-92 fixed for empty set */
  233.                                     /* WEC 12-1-92 fixed for c.n = 0 */
  234.     set_ext(&t, b.n);
  235.     r = t.setword;
  236.  
  237.     /* Dif b,c until smaller set size */
  238.     q = c.setword;
  239.     p = b.setword;
  240.     endp = &(b.setword[n]);
  241.     while ( p < endp ) *r++ = *p++ & (~ *q++);    
  242.  
  243.     /* Copy rest of b into result if size(b) > c */
  244.     if ( b.n > n )
  245.     {
  246.         p = &(b.setword[n]);
  247.         endp = &(b.setword[b.n]);
  248.         while ( p < endp ) *r++ = *p++;
  249.     }
  250.  
  251.     return(t);
  252. }
  253.  
  254. set
  255. #ifdef __STDC__
  256. set_of( unsigned b )
  257. #else
  258. set_of( b )
  259. unsigned b;
  260. #endif
  261. {
  262.     /* Fast singleton set constructor operation */
  263.     static set a;
  264.  
  265.     if ( b == nil ) return( empty );
  266.     set_new(a, b);
  267.     a.setword[DIVWORD(b)] = bitmask[MODWORD(b)];
  268.  
  269.     return(a);
  270. }
  271.  
  272. /*
  273.  * Extend (or shrink) the set passed in to have n words.
  274.  *
  275.  * if n is smaller than the minimum, boost n to have the minimum.
  276.  * if the new set size is the same as the old one, do nothing.
  277.  *
  278.  * TJP 4-27-92 Fixed so won't try to alloc 0 bytes
  279.  */
  280. void
  281. #ifdef __STDC__
  282. set_ext( set *a, unsigned int n )
  283. #else
  284. set_ext( a, n )
  285. set *a;
  286. unsigned int n;
  287. #endif
  288. {
  289.     register unsigned *p;
  290.     register unsigned *endp;
  291.     unsigned int size;
  292.     
  293.     CHK((*a));
  294.     if ( a->n == 0 )
  295.     {
  296.         if ( n == 0 ) return;
  297.         a->setword = (unsigned *) calloc(n, BytesPerWord);
  298.         if ( a->setword == NULL )
  299.         {
  300.             fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  301.             exit(-1);
  302.         }
  303.         a->n = n;
  304.         return;
  305.     }
  306.     if ( n < min ) n = min;
  307.     if ( a->n == n || n == 0 ) return;
  308.     size = a->n;
  309.     a->n = n;
  310.     a->setword = (unsigned *) realloc( (char *)a->setword, (n*BytesPerWord) );
  311.     if ( a->setword == NULL )
  312.     {
  313.         fprintf(stderr, "set_ext(%d words): cannot allocate set\n", n);
  314.         exit(-1);
  315.     }
  316.  
  317.     p    = &(a->setword[size]);        /* clear from old size to new size */
  318.     endp = &(a->setword[a->n]);
  319.     do {
  320.         *p++ = 0;
  321.     } while ( p < endp );
  322. }
  323.  
  324. set
  325. #ifdef __STDC__
  326. set_not( set a )
  327. #else
  328. set_not( a )
  329. set a;
  330. #endif
  331. {
  332.     /* Fast not of set a (assumes all bits used) */
  333.     /* size of resultant set is size(a) */
  334.     /* ~empty = empty cause we don't know how bit to make set */
  335.     set t;
  336.     register unsigned *r;
  337.     register unsigned *p = a.setword;
  338.     register unsigned *endp = &(a.setword[a.n]);
  339.  
  340.     CHK(a);
  341.     t = empty;
  342.     if ( a.n == 0 ) return( empty );
  343.     set_ext(&t, a.n);
  344.     r = t.setword;
  345.     
  346.     do {
  347.         *r++ = (~ *p++);
  348.     } while ( p < endp );
  349.  
  350.     return(t);
  351. }
  352.  
  353. int
  354. #ifdef __STDC__
  355. set_equ( set a, set b )
  356. #else
  357. set_equ( a, b )
  358. set a;
  359. set b;
  360. #endif
  361. {
  362.     /* Fast set equality comparison operation */
  363.     register unsigned *p = a.setword;
  364.     register unsigned *q = b.setword;
  365.     register unsigned *endp = &(a.setword[a.n]);
  366.  
  367.     CHK(a); CHK(b);
  368. /*    if ( a.n != b.n ) return(0);*/
  369.     if ( set_deg(a) != set_deg(b) ) return(0);
  370.     else if ( a.n==0 ) return(1);    /* empty == empty */
  371.     
  372.     do {
  373.         if (*p != *q) return(0);
  374.         ++q;
  375.     } while ( ++p < endp );
  376.  
  377.     return(1);
  378. }
  379.  
  380. int
  381. #ifdef __STDC__
  382. set_sub( set a, set b )
  383. #else
  384. set_sub( a, b )
  385. set a;
  386. set b;
  387. #endif
  388. {
  389.     /* Fast check for a is a proper subset of b (alias a < b) */
  390.     register unsigned *p = a.setword;
  391.     register unsigned *q = b.setword;
  392.     register unsigned *endp = &(a.setword[a.n]);
  393.     register int asubset = 0;
  394.  
  395.     CHK(a); CHK(b);
  396.     if ( set_deg(a) > set_deg(b) ) return(0);
  397.     if ( set_deg(a)==0 && set_deg(b)==0) return(1);/* empty prop sub of empty */
  398.     if ( set_deg(a) == 0 ) return(1);        /* empty is sub of everything */
  399. #ifdef DUH
  400. /* Was: */
  401.     if ( a.n > b.n ) return(0);
  402.     if (a.n==0 && b.n==0) return(1);/* empty prop sub of empty */
  403.     if ( a.n == 0 ) return(1);        /* empty is sub of everything */
  404. #endif
  405.  
  406.     do {
  407.         /* Prune tests based on guess that most set words
  408.            will match, particularly if a is a subset of b.
  409.         */
  410.         if (*p != *q) {
  411.             if (*p & ~(*q)) {
  412.                 /* Fail -- a contains something b does not */
  413.                 return(0);
  414.             }
  415.             /* At least this word was a proper subset, hence
  416.                even if all other words are equal, a is a
  417.                proper subset of b.
  418.             */
  419.             asubset = 1;
  420.         }
  421.         ++q;
  422.     } while (++p < endp);
  423.  
  424.     /* at this point, a,b are equ or a subset */
  425.     if ( asubset || b.n == a.n ) return(asubset);
  426.     
  427.     /* if !asubset, size(b) > size(a), then a=b and must check rest of b */
  428.     p = q;
  429.     endp = &(b.setword[b.n]);
  430.     do
  431.     {
  432.         if ( *p++ ) return(1);
  433.     } while ( p < endp );
  434.  
  435.     return(0);
  436. }
  437.  
  438. unsigned
  439. #ifdef __STDC__
  440. set_int( set b )
  441. #else
  442. set_int( b )
  443. set b;
  444. #endif
  445. {
  446.     /* Fast pick any element of the set b */
  447.     register unsigned *p = b.setword;
  448.     register unsigned *endp = &(b.setword[b.n]);
  449.  
  450.     CHK(b);
  451.     if ( b.n == 0 ) return( nil );
  452.  
  453.     do {
  454.         if (*p) {
  455.             /* Found a non-empty word of the set */
  456.             register unsigned i = ((p - b.setword) << LogWordSize);
  457.             register unsigned t = *p;
  458.             p = &(bitmask[0]);
  459.             while (!(*p & t)) {
  460.                 ++i; ++p;
  461.             }
  462.             return(i);
  463.         }
  464.     } while (++p < endp);
  465.  
  466.     /* Empty -- only element it contains is nil */
  467.     return(nil);
  468. }
  469.  
  470. int
  471. #ifdef __STDC__
  472. set_el( unsigned b, set a )
  473. #else
  474. set_el( b, a )
  475. unsigned b;
  476. set a;
  477. #endif
  478. {
  479.     CHK(a);
  480.     /* nil is an element of every set */
  481.     if (b == nil) return(1);
  482.     if ( a.n == 0 || NumWords(b) > a.n ) return(0);
  483.     
  484.     /* Otherwise, we have to check */
  485.     return( a.setword[DIVWORD(b)] & bitmask[MODWORD(b)] );
  486. }
  487.  
  488. int
  489. #ifdef __STDC__
  490. set_nil( set a )
  491. #else
  492. set_nil( a )
  493. set a;
  494. #endif
  495. {
  496.     /* Fast check for nil set */
  497.     register unsigned *p = a.setword;
  498.     register unsigned *endp = &(a.setword[a.n]);
  499.  
  500.     CHK(a);
  501.     if ( a.n == 0 ) return(1);
  502.     /* The set is not empty if any word used to store
  503.        the set is non-zero.  This means one must be a
  504.        bit careful about doing things like negation.
  505.     */
  506.     do {
  507.         if (*p) return(0);
  508.     } while (++p < endp);
  509.     
  510.     return(1);
  511. }
  512.  
  513. char *
  514. #ifdef __STDC__
  515. set_str( set a )
  516. #else
  517. set_str( a )
  518. set a;
  519. #endif
  520. {
  521.     /* Fast convert set a into ASCII char string...
  522.        assumes that all word bits are used in the set
  523.        and that SETSIZE is a multiple of WORDSIZE.
  524.        Trailing 0 bits are removed from the string.
  525.        if no bits are on or set is empty, "" is returned.
  526.     */
  527.     register unsigned *p = a.setword;
  528.     register unsigned *endp = &(a.setword[a.n]);
  529.     static char str_tmp[StrSize+1];
  530.     register char *q = &(str_tmp[0]);
  531.  
  532.     CHK(a);
  533.     if ( a.n==0 ) {*q=0; return( &(str_tmp[0]) );}
  534.     do {
  535.         register unsigned t = *p;
  536.         register unsigned *b = &(bitmask[0]);
  537.         do {
  538.             *(q++) = (char) ((t & *b) ? '1' : '0');
  539.         } while (++b < &(bitmask[WORDSIZE]));
  540.     } while (++p < endp);
  541.  
  542.     /* Trim trailing 0s & NULL terminate the string */
  543.     while ((q > &(str_tmp[0])) && (*(q-1) != '1')) --q;
  544.     *q = 0;
  545.  
  546.     return(&(str_tmp[0]));
  547. }
  548.  
  549. set
  550. #ifdef __STDC__
  551. set_val( register char *s )
  552. #else
  553. set_val( s )
  554. register char *s;
  555. #endif
  556. {
  557.     /* Fast convert set ASCII char string into a set.
  558.        If the string ends early, the remaining set bits
  559.        are all made zero.
  560.        The resulting set size is just big enough to hold all elements.
  561.     */
  562.     static set a;
  563.     register unsigned *p, *endp;
  564.  
  565.     set_new(a, strlen(s));
  566.     p = a.setword;
  567.     endp = &(a.setword[a.n]);
  568.     do {
  569.         register unsigned *b = &(bitmask[0]);
  570.         /* Start with a word with no bits on */
  571.         *p = 0;
  572.         do {
  573.             if (*s) {
  574.                 if (*s == '1') {
  575.                     /* Turn-on this bit */
  576.                     *p |= *b;
  577.                 }
  578.                 ++s;
  579.             }
  580.         } while (++b < &(bitmask[WORDSIZE]));
  581.     } while (++p < endp);
  582.  
  583.     return(a);
  584. }
  585.  
  586. /*
  587.  * Or element e into set a.  a can be empty.
  588.  */
  589. void
  590. #ifdef __STDC__
  591. set_orel( unsigned e, set *a )
  592. #else
  593. set_orel( e, a )
  594. unsigned e;
  595. set *a;
  596. #endif
  597. {
  598.     CHK((*a));
  599.     if ( e == nil ) return;
  600.     if ( NumWords(e) > a->n ) set_ext(a, NumWords(e));
  601.     a->setword[DIVWORD(e)] |= bitmask[MODWORD(e)];
  602. }
  603.  
  604. /*
  605.  * Or set b into set a.  a can be empty. does nothing if b empty.
  606.  */
  607. void
  608. #ifdef __STDC__
  609. set_orin( set *a, set b )
  610. #else
  611. set_orin( a, b )
  612. set *a;
  613. set b;
  614. #endif
  615. {
  616.     /* Fast set union operation */
  617.     /* size(a) is max(a, b); */
  618.     unsigned int m;
  619.     register unsigned *p,
  620.                       *q    = b.setword,
  621.                       *endq = &(b.setword[b.n]);
  622.  
  623.     CHK((*a)); CHK(b);
  624.     if ( b.n == 0 ) return;
  625.     m = (a->n > b.n) ? a->n : b.n;
  626.     set_ext(a, m);
  627.     p = a->setword;
  628.     do {
  629.         *p++ |= *q++;
  630.     } while ( q < endq );
  631. }
  632.  
  633. void
  634. #ifdef __STDC__
  635. set_rm( unsigned e, set a )
  636. #else
  637. set_rm( e, a )
  638. unsigned e;
  639. set a;
  640. #endif
  641. {
  642.     /* Does not effect size of set */
  643.     CHK(a);
  644.     if ( (e == nil) || (NumWords(e) > a.n) ) return;
  645.     a.setword[DIVWORD(e)] ^= (a.setword[DIVWORD(e)]&bitmask[MODWORD(e)]);
  646. }
  647.  
  648. void
  649. #ifdef __STDC__
  650. set_clr( set a )
  651. #else
  652. set_clr( a )
  653. set a;
  654. #endif
  655. {
  656.     /* Does not effect size of set */
  657.     register unsigned *p = a.setword;
  658.     register unsigned *endp = &(a.setword[a.n]);
  659.     
  660.     CHK(a);
  661.     if ( a.n == 0 ) return;
  662.     do {
  663.         *p++ = 0;
  664.     } while ( p < endp );
  665. }
  666.  
  667. set
  668. #ifdef __STDC__
  669. set_dup( set a )
  670. #else
  671. set_dup( a )
  672. set a;
  673. #endif
  674. {
  675.     set b;
  676.     register unsigned *p,
  677.                       *q    = a.setword,
  678.                       *endq = &(a.setword[a.n]);
  679.     
  680.     CHK(a);
  681.     b = empty;
  682.     if ( a.n == 0 ) return( empty );
  683.     set_ext(&b, a.n);
  684.     p = b.setword;
  685.     do {
  686.         *p++ = *q++;
  687.     } while ( q < endq );
  688.     
  689.     return(b);
  690. }
  691.  
  692. /*
  693.  * Return a nil terminated list of unsigned ints that represents all
  694.  * "on" bits in the bit set.
  695.  *
  696.  * e.g. {011011} --> {1, 2, 4, 5, nil}
  697.  *
  698.  * _set_pdq and set_pdq are useful when an operation is required on each element
  699.  * of a set.  Normally, the sequence is:
  700.  *
  701.  *        while ( set_deg(a) > 0 ) {
  702.  *            e = set_int(a);
  703.  *            set_rm(e, a);
  704.  *            ...process e...
  705.  *        }
  706.  * Now,
  707.  *
  708.  *        t = e = set_pdq(a);
  709.  *        while ( *e != nil ) {
  710.  *            ...process *e...
  711.  *            e++;
  712.  *        }
  713.  *        free( t );
  714.  *
  715.  * We have saved many set calls and have not destroyed set a.
  716.  */
  717. void
  718. #ifdef __STDC__
  719. _set_pdq( set a, register unsigned *q )
  720. #else
  721. _set_pdq( a, q )
  722. set a;
  723. register unsigned *q;
  724. #endif
  725. {
  726.     register unsigned *p = a.setword,
  727.                       *endp = &(a.setword[a.n]);
  728.     register unsigned e=0;
  729.  
  730.     CHK(a);
  731.     /* are there any space (possibility of elements)? */
  732.     if ( a.n == 0 ) return;
  733.     do {
  734.         register unsigned t = *p;
  735.         register unsigned *b = &(bitmask[0]);
  736.         do {
  737.             if ( t & *b ) *q++ = e;
  738.             ++e;
  739.         } while (++b < &(bitmask[WORDSIZE]));
  740.     } while (++p < endp);
  741.     *q = nil;
  742. }
  743.  
  744. /*
  745.  * Same as _set_pdq except allocate memory.  set_pdq is the natural function
  746.  * to use.
  747.  */
  748. unsigned *
  749. #ifdef __STDC__
  750. set_pdq( set a )
  751. #else
  752. set_pdq( a )
  753. set a;
  754. #endif
  755. {
  756.     unsigned *q;
  757.     int max_deg;
  758.     
  759.     CHK(a);
  760.     max_deg = WORDSIZE*a.n;
  761.     /* assume a.n!=0 & no elements is rare, but still ok */
  762.     if ( a.n == 0 ) return(NULL);
  763.     q = (unsigned *) malloc((max_deg+1)*BytesPerWord);
  764.     if ( q == NULL ) return( NULL );
  765.     _set_pdq(a, q);
  766.     return( q );
  767. }
  768.  
  769. /* a function that produces a hash number for the set
  770.  */
  771. unsigned int
  772. #ifdef __STDC__
  773. set_hash( set a, register unsigned int mod )
  774. #else
  775. set_hash( a, mod )
  776. set a;
  777. register unsigned int mod;
  778. #endif
  779. {
  780.     /* Fast hash of set a (assumes all bits used) */
  781.     register unsigned *p = &(a.setword[0]);
  782.     register unsigned *endp = &(a.setword[a.n]);
  783.     register unsigned i = 0;
  784.  
  785.     CHK(a);
  786.     while (p<endp){
  787.         i += (*p);
  788.         ++p;
  789.     }
  790.  
  791.     return(i % mod);
  792. }
  793.